#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;
        if (root->val > p->val && root->val > q->val)
        {
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            if (left != nullptr)
                return left;
        }
        else if (root->val < p->val && root->val < q->val)
        {
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            if (right != nullptr)
                return right;
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        if (root == nullptr)
        {
            root = new TreeNode(val);
            return root;
        }
        while (cur)
        {
            if (cur->val > val)
            {
                prev = cur;
                cur = cur->left;
            }
            else
            {
                prev = cur;
                cur = cur->right;
            }
        }
        cur = new TreeNode(val);
        if (prev->val > cur->val)
            prev->left = cur;
        else
            prev->right = cur;
        return root;
    }
};

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while (cur)
        {
            if (cur->val > key)
            {
                prev = cur;
                cur = cur->left;
            }
            else if (cur->val < key)
            {
                prev = cur;
                cur = cur->right;
            }
            else
            {
                if (cur->right == nullptr)
                {
                    if (cur == root)
                        root = cur->left;
                    else
                        if (prev->left == cur)
                            prev->left = cur->left;
                        else
                            prev->right = cur->left;
                    delete cur;
                }
                else if (cur->left == nullptr)
                {
                    if (cur == root)
                        root = cur->right;
                    else
                        if (prev->left == cur)
                            prev->left = cur->right;
                        else
                            prev->right = cur->right;
                    delete cur;
                }
                else
                {
                    TreeNode* ptmp = cur;
                    TreeNode* tmp = cur->right;
                    while (tmp->left)
                    {
                        ptmp = tmp;
                        tmp = tmp->left;
                    }
                    cur->val = tmp->val;
                    if (ptmp->right == tmp) {
                        ptmp->right = tmp->right;
                    }
                    else
                        ptmp->left = tmp->right;
                    delete tmp;
                }
                break;
            }
        }
        return root;
    }
};